package org.niu.tree;

import java.util.ArrayList;
import java.util.List;

public class PathSum2 {
    ArrayList<Integer> l = new ArrayList<>();
    ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> pathSum (TreeNode root, int sum) {
        // write code here
        dfs(root,sum);
        return ans;
    }

    void dfs(TreeNode root, int sum){
        if(root == null) return;

        if(sumList(l) == sum && root.left == null && root.right == null){
            ans.add(l);
            return;
        }
        l.add(root.val);
        dfs(root.left,sum);
        dfs(root.right,sum);
        l.remove(l.size()-1);
    }

    public int sumList(ArrayList<Integer> list){
        int sum = 0;
        for (int i = 0; i < list.size(); i++) {
            sum += list.get(i);
        }
        return  sum;
    }
}
